#include <iostream>
#include <set>
using namespace std;

void test1()
{
	set<int> s;
	s.insert(5); s.insert(5);
	s.insert(2); s.insert(2);
	s.insert(1);
	s.insert(9);
	s.insert(7);

	//set<int>::iterator it = s.begin();
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	auto rit = s.rbegin();
	while (rit != s.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

	int x;
	cin >> x;

	if (s.find(x) != s.end()) cout << "存在" << endl;
	else cout << "不存在" << endl;

	auto pos1 = find(s.begin(), s.end(), x); //O(N)
	auto pos2 = s.find(x); // O(log(N))

	if (s.count(x))  //O(log(N))
		cout << "存在" << endl;
	else cout << "不存在" << endl;

	s.insert(x);
	cout << "插入：";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	cout << "删除：";
	s.erase(s.begin(),s.end());
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;



}

void test2()
{
	std::set<int> myset;
	std::set<int>::iterator itlow, itup;
	
	for (int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
	
	// [30, 60]
	// >= 30

	itlow = myset.lower_bound(24);                //
	// > 60
	itup = myset.upper_bound(34);         
	cout << *itlow << " " << *itup << endl;

	myset.erase(itlow, itup);                     // 10 20 70 80 90

	std::cout << "myset contains:";
	for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it)
	    std::cout << ' ' << *it;
	std::cout << '\n';
}


void test3()
{
	multiset<int> s;
	s.insert(5); s.insert(5);
	s.insert(2); s.insert(2); s.insert(2);
	s.insert(1);
	s.insert(9);
	s.insert(7);

	//set<int>::iterator it = s.begin();
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;


	int x;
	cin >> x;
	auto pos = s.find(x); //查找x时，返回中序第一个
	while (pos != s.end() && *pos == x)  
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl;

}

int main()
{
	test2();


	return 0;
}